import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        int a=0;
        System.out.println(a);
    }
    //最⻓湍流⼦数组
    public int maxTurbulenceSize(int[] arr) {
        int n=arr.length;
        int[] f=new int[n];
        int[] g=new int[n];
        int ret=1;
        for(int i=0;i<n;i++){
            f[i]=g[i]=1;
        }
        for(int i=1;i<n;i++){
            if(arr[i]>arr[i-1]){
                f[i]=g[i-1]+1;
            }else if(arr[i]<arr[i-1]){
                g[i]=f[i-1]+1;
            }
            ret=Math.max(ret,Math.max(f[i],g[i]));
        }
        return ret;
    }


    //单词拆分
    public boolean wordBreak(String s, List<String> wordDict) {
        //优化一：将字典先存储在Hash表中，减少后面查询时间
        Set<String> hashSet=new HashSet<>(wordDict);

        int n=s.length();
        boolean[] dp=new boolean[n+1];
        dp[0]=true;
        //这里加上一个" "是为了映射字符串下标为0的位置
        s=" "+s;
        for(int i=1;i<=n;i++){
            for(int j=i;j>=1;j--){
                if(dp[j-1]&& hashSet.contains(s.substring(i,j+1))){
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[n];
    }
}